home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 1 / Cream of the Crop 1.iso / PROGRAM / TON_O_C.ARJ / QSORT.C < prev    next >
C/C++ Source or Header  |  1992-01-02  |  5KB  |  180 lines
  1. #define DEBUG
  2. /*    qsort - general purpose quicksort 
  3.  
  4.     Author...
  5.         Copyright (c) 1984  Allen I. Holub
  6.  
  7.         All rights reserved.
  8.         This program may be copied for personal, non-profit use only.
  9.  
  10.         Published in Dr. Dobb's Journal #102 (Apr 85).
  11.  
  12.     Usage...
  13.  
  14.         Including a #define for DEBUG will make this file a stand-alone
  15.         program which sorts argv and prints the result, along with all
  16.         intermediate stages.  This is pretty instructive if you want to
  17.         see how the quick sort works.
  18.  
  19. */
  20.  
  21. #ifdef DEBUG
  22.  
  23. static int    Lev=0;        /* recursion level */
  24. static int    Maxlev=0;    /* maximum recursion level */
  25. int Comparisons=0, Exchanges=0;
  26. #endif
  27.  
  28. typedef int (*PFI)();    /* pointer to a function returning int */
  29. static PFI Comp;        /* pointer to comparison routine */
  30. static int Width;        /* width of an object in bytes */
  31.  
  32. /*---------------------------------------------------------------------------*/
  33. int argvcmp(s1p,s2p) char **s1p,**s2p;
  34. {
  35.     /*    Comparison routine for sorting an argv like list of pointers
  36.         to strings.  Just remove one level of indirection and call
  37.         strcmp to do the comparison                                        */
  38.  
  39. #ifdef DEBUG
  40.     register int rval;
  41.     rval=strcmp(*s1p,*s2p);
  42.     printf("level %d: argvcmp(<%s><%s>) = %d\n",Lev,*s1p,*s2p,rval);
  43.     Comparisons++;
  44.     return (rval);
  45. #else
  46.     return (strcmp(*s1p,*s2p));
  47. #endif
  48. }
  49.  
  50. qsort(base,nel,width,compare)
  51. char *base;
  52. int    nel,width;
  53. int    (*compare)();
  54. {
  55.     /*    Perform a quick sort on an array starting at base.  The
  56.         array is nel elements large and width is the size of a single
  57.         element in bytes.  Compare is a pointer to a comparison routine
  58.         which will be passed pointers to two elements of the array.  It
  59.         should return a negative number if the left-most argument is
  60.         less than the rightmost, 0 if the two arguments are equal, a
  61.         positive number if the left argument is greater than the right. 
  62.         (That is, it acts like a "subtract" operator.) If compare is 0
  63.         then the default comparison routine, argvcmp (which sorts an
  64.         argv-like array of pointers to strings), is used.
  65.     */
  66.  
  67. #ifdef DEBUG
  68.     printf("Sorting %d element array of %d byte elements at 0x%x\n",
  69.         nel,width,base);
  70.     printf("Comparison routine at 0x%x. Unsorted list:\n",compare);
  71.     ptext(nel,base);
  72. #endif
  73.     Width=width;
  74.     Comp=(compare==(PFI)0) ? &argvcmp : compare ;
  75.     if(nel>1)
  76.         rqsort(base,base+((nel-1)*width));
  77. #ifdef DEBUG
  78.     printf("\nSort complete, list is:\n");
  79.     ptext(nel,base);
  80.     printf("Maximum recursion level = %d\n",Maxlev);
  81.     printf("%d comparisons and %d exchanges were performed \n",
  82.     Comparisons, Exchanges);
  83. #endif
  84. }
  85.  
  86. /*---------------------------------------------------------------------------*/
  87. static rqsort(low,high)
  88. register char *low,*high;
  89. {
  90.     /*    Workhorse function called by the access routine, qsort().
  91.         Not externally accessible.                                        */
  92.  
  93.     char *pivot,*base;
  94.     static char *a,*b;    /*    Used for exchanges, will not need to retain    */
  95.     static int tmp,i;    /*    their values during the recursion so they    */
  96.                         /*    can be static                                */
  97.     
  98. #ifdef DEBUG
  99.     printf("New pass, recursion level %d\n",Lev);
  100.     if (Lev>Maxlev) Maxlev=Lev;
  101. #endif
  102.     base=low;        /* remember base address of array    */
  103.     pivot=high;        /* partition off the pivot            */
  104.     high -= Width;
  105.  
  106.     do
  107.         {while( low<high && (*Comp)(low,pivot) <= 0)  low += Width;
  108.         while( low<high && (*Comp)(high,pivot) >= 0 ) high -= Width;
  109.         if( low < high )    /* exchange low & high */
  110.             {
  111. #ifdef DEBUG
  112.             printf("lev %d: exchanging high: <%s> & low: <%s>\n",
  113.                 Lev,*((char **)high), *((char **)low));
  114. #endif
  115.             for ( b=low,a=high,i=Width ; --i>=0 ; )
  116.                 {tmp = *b;    /* Exchange *low and *high */
  117.                 *b++ = *a;
  118.                 *a++ = tmp;
  119. #ifdef DEBUG
  120.     Exchanges++;
  121. #endif
  122.                 }
  123.             }
  124.         } while ( low<high );
  125. #ifdef DEBUG
  126.         printf("level %d: Exchanging pivot:<%s>  & low:<%s>\n",
  127.             Lev, *((char **)pivot), *((char**)low) );
  128. #endif
  129.         if( low < pivot && (*Comp)(low, pivot) > 0 )
  130.             for ( b=low,a=pivot,i=Width ; --i >=0 ; )
  131.                 {tmp=*b ;    /* Exchange *low and *pivot */
  132.                 *b++=*a;
  133.                 *a++=tmp;
  134. #ifdef DEBUG
  135.     Exchanges++;
  136. #endif
  137.                 }
  138. #ifdef DEBUG
  139.         printf("\nDone with pass, partially sorted list =\n");
  140.         ptext( ((pivot - base)/Width) + 1,base );
  141.         printf("\n");
  142.         ++Lev;
  143. #endif
  144.         low += Width;
  145.         if( high-base < pivot-low )
  146.             {if( low < pivot ) rqsort( low , pivot );
  147.             if(base < high ) rqsort( base , high );
  148.             }
  149.         else
  150.             {if( base < high ) rqsort( base , high );
  151.             if( low < pivot ) rqsort( low , pivot );
  152.             }
  153. #ifdef DEBUG
  154.         --Lev;
  155. #endif
  156. }
  157.         
  158. /*---------------------------------------------------------------------------*/
  159. /*        Test routine for qsort, compiled if DEBUG is #defined                */
  160.  
  161. #ifdef DEBUG
  162. static ptext( argc, argv)
  163. int argc;
  164. char **argv;
  165. {
  166.     /*    Print out argv, one element per line    */
  167.  
  168.     register int i;
  169.     for ( i=1 ; --argc>=0 ; i++ ) printf("%2d: %s\n",i,*argv++);
  170. }
  171.  
  172. main(argc,argv) int argc; char **argv;
  173. {    
  174.     /*    Test routine for qsort.  Sorts argv (less the first element).    */
  175.  
  176.     qsort(++argv,--argc,sizeof(PFI),0);
  177. }
  178.  
  179. #endif
  180.